package org.algorithm.熊猫.数组.二月;

/***
 * 给你一个整数数组 nums 。nums 中，子数组的 范围 是子数组中最大元素和最小元素的差值。
 *
 * 返回 nums 中 所有 子数组范围的 和 。
 *
 * 子数组是数组中一个连续 非空 的元素序列。
 *
 * @author 熊猫
 * @date 2022/3/04 13:30:01 星期五
 * uri:  https://leetcode-cn.com/problems/sum-of-subarray-ranges/
 */
public class 子数组范围和 {

    public static void main(String[] args) {
        int[] nums = {1, 2, 3,4};
        System.out.println(subArrayRanges(nums));
    }


    /**
     *  双循环  时间复杂度o(n2)
     * @param nums
     * @return
     */
    public static long subArrayRanges(int[] nums) {
        long sum = 0;

        for (int i = 0; i < nums.length; i++) {
            long max = Long.MIN_VALUE, min = Long.MAX_VALUE;
            for (int j = i; j < nums.length; j++) {
                max = Math.max(max, nums[j]);
                min = Math.min(min, nums[j]);
                sum += (max - min);
            }
        }

        return sum;
    }

    /**
     *  双循环  单调栈
     * @param nums
     * @return
     */
    public static long subArrayRanges2(int[] nums) {
        return -1;
    }

}
